home *** CD-ROM | disk | FTP | other *** search
- @if-using not(MAZE-MAC)
- @use (MAZE-MAC)
- @use (SHOW-PATH) ; the current path is marked with o (SLOWER)
- @if-using (SHOW-PATH)
- ;@use (HIDE_SEARCH) ; don't display the search, only the result
- @fi
- ;OCL{{{}}}
- ;OCL{{{ description of the problem and its solution
- ;OCL{{{ the algorithm
- ; These macros 'solve' any maze produced by the a-maze-ing maze.c program.
- ;
- ; First, a bit of maze theory.
- ; If you were put into a maze, a guaranteed method of finding your way
- ; out of the maze is to put your left hand onto a wall and just keep walking,
- ; never taking your hand off the wall. This technique is only guaranteed to
- ; work if the maze does not have any 'islands', or if the 'exit' is on the
- ; same island as your starting point. These conditions hold for the mazes
- ; under consideration.
- ;
- ; Assuming that the maze is made up of horizontal and vertical walls spaced
- ; one step apart and that you can move either north, south, east or west,
- ; then you can automate this procedure by carrying out the following steps.
- ;
- ; 1. Put yourself somewhere in the maze near a wall.
- ; 2. Check if you have a wall on your left. If so, go to step 4.
- ; 3. There is no wall on your left, so turn on the spot to your left and step
- ; forward by one step and repeat step 2.
- ; 4. Check what is directly in front of you. If it is a wall, turn on the
- ; spot to your right by 90 degrees and repeat step 4.
- ; 5. There is no wall in front of you, so step forward one step and
- ; go to step 2.
- ;OCL}}}
- ;OCL{{{ the used maze-format
- ; By examining a maze produced by the maze.c program you will see that
- ; each square of the maze is one character high and two characters wide.
- ; To go north or south, you move by a one character step, but to move east or
- ; west you move by a two character step. Also note that in any position
- ; there are four places where walls could be put - to the north, to the south,
- ; to the east and to the west.
- ; A wall exists to the north of you if the character to the north of
- ; you is a _ (otherwise it is a space).
- ; A wall exists to the east of you if the character to the east of you
- ; is a | (otherwise it is a .).
- ; A wall exists to the west of you if the character to the west of you
- ; is a | (otherwise it is a .).
- ; A wall exists to the south of you if the character where you are
- ; is a _ (otherwise it is a space).
- ;OCL}}}
- ;OCL{{{ implementation
- ; i implemented it with a couple of macros
- ; maze-step - do one of the above mentioned steps of
- ; the algorithm
- ; set-destination -
- ; check the current cursor-position to be a correct
- ; destination-point. (Its a little bit simple, if you
- ; are not in the maze, it will not work correct).
- ; get-new-maze -
- ; append at the end of ypur text a new maze.
- ; the command 'maze' must be available.
- ;
- ; all other macros are help-functions
- ;
- ; used variables:
- ; maze-dir: direction of movement
- ; 0 - up
- ; 1 - left
- ; 2 - down
- ; 3 - right
- ; maze-state: state of the machine like above
- ; maze-front: is set by front-wall, if there is a wall
- ;OCL}}}
- ;OCL{{{ how to do it
- ; 0. Put the command maze in your path. This is the same a for vi and the
- ; used maze-format is the same too!
- ; 1. put the following macros in your OCL-file and make a new .origamirc .
- ; 2. Choose keybindings for the macros maze-step, get-new-maze, set-destination
- ; 3. get a maze with get-new-maze
- ; 4. go into the maze and set the destination with set-destination
- ; 5. do maze-stepo and it runs!!!
- ;OCL}}}
- ;OCL}}}
- ;OCL{{{ libs
- @lib delchar
- ;OCL}}}
- ;OCL{{{ vars
- ( defvar
- ( maze-dir ; direction to go
- maze-front ; what is in front of me
- maze-x-pos ; current cursor-position
- maze-y-pos
- maze-begin-line ; first state in the maze
- maze-state ; code the current state of the automata
- maze-new-x-pos
- maze-new-y-pos
- go-line-arg-
- x
- case-0
- case-1
- case-2
- case-3
- case-4
- case-5
- )
- )
- ;OCL}}}
- ;OCL{{{ help-functions
- ;OCL{{{ turn-left
- (deffun turn-left (
- if =(maze-dir 0) (
- set maze-dir 3
- ) else (
- set maze-dir +(maze-dir -1)
- )fi
- )
- )
- ;OCL}}}
- ;OCL{{{ test-case
- (deffun test-case (
- set case-1 +(case-0 -1)
- set case-2 +(case-0 -2)
- set case-3 +(case-0 -3)
- set case-4 +(case-0 -4)
- set case-5 +(case-0 -5)
- ))
- ;OCL}}}
- ;OCL{{{ front-wall
- (deffun front-wall (
- set maze-front 0
- set case-0 maze-dir
- test-case
- case
- ;OCL{{{ dir up
- (=(case-0 0) (
- previous-line
- if or(test-char "_ test-char "O) (set maze-front 1) fi
- next-line
- ))
- ;OCL}}}
- ;OCL{{{ dir left
- (=(case-1 0) (
- backward-character
- if test-char "| (set maze-front 1) fi
- forward-character
- ))
- ;OCL}}}
- ;OCL{{{ dir down
- (=(case-2 0) (
- if or(test-char "_ test-char "O) (set maze-front 1) fi
- ))
- ;OCL}}}
- ;OCL{{{ dir right
- (=(case-3 0) (
- forward-character
- if test-char "| (set maze-front 1) fi
- backward-character
- ))
- ;OCL}}}
- default (message-exit "incorrect_dir_in_front)
- esac
- ))
- ;OCL}}}
- ;OCL{{{ go
- ;OCL{{{ go-line-
- ( deffun go-line-
- ( local
- ( go-line-arg- )
- ( while
- pre
- ( set x -(go-line-arg- store-line) )
- <>(x 0)
- ;OCL{{{ one step to correct line
- ( if >(x 0)
- ;OCL{{{ down
- ( if test-bottom
- ( @if-using (SCR-OFF)
- screen-on
- redraw-display
- @fi
- return-from-macro
- )
- fi
- next-line
- )
- ;OCL}}}
- else
- ;OCL{{{ up
- ( if test-top ( return-from-macro ) fi
- previous-line
- ;OCL{{{ on fold?, maybe down again
- if or(test-fold-line,test-filed)
- ( set x -(go-line-arg- store-line)
- if =(x 0) ( return-from-macro ) fi
- ;OCL{{{ maybe skip to end of this fold
- if >(x 0)
- ( if test-filed ( return-from-macro ) fi
- open-fold
- mtool-bot
- )
- fi
- ;OCL}}}
- )
- fi
- ;OCL}}}
- )
- ;OCL}}}
- fi
- )
- ;OCL}}}
- )
- )
- )
- ;OCL}}}
- (deffun go (
- set maze-x-pos store-pos
- set maze-y-pos store-line
- case
- @if-using (SHOW-PATH)
- (test-char " ("o ))
- (test-char "_ ("O ))
- @fi
- default (forward-character)
- esac
- backward-character
- set case-0 maze-dir
- test-case
- case
- (=(case-0 0) (previous-line))
- (=(case-1 0) (backward-character backward-character))
- (=(case-2 0) (next-line))
- (=(case-3 0) (forward-character forward-character))
- default (message-exit "incorrect_dir_in_go)
- esac
- @if-using (SHOW-PATH)
- if or(test-char "o test-char "O) (
- set maze-new-x-pos store-pos
- set maze-new-y-pos store-line
- set go-line-arg- maze-y-pos
- go-line-
- goto-counter maze-x-pos
- case
- (test-char " ("o ))
- (test-char "_ ("O ))
- (test-char "o (" ))
- (test-char "O ("_ ))
- default (message-exit "invalid_maze )
- esac
- set go-line-arg- maze-new-y-pos
- go-line-
- goto-counter maze-new-x-pos
- ) fi
- @fi
- ))
- ;OCL}}}
- ;OCL}}}
- ;OCL{{{ get new maze
- (deffun get-new-maze (
- beginning-of-fold
- beginning-of-line
- set maze-begin-line +(store-line 1)
- next-line
- pipe-from-command
- "maze
- newline-and-indent
- message-exit "new_maze_read
- ))
- ;OCL}}}
- ;OCL{{{ set-destination
- (deffun set-destination (
- if or(test-char " ,test-char "_)
- (delete-character "X )
- else
- (message-exit "no_correct_position)
- fi
- ))
- ;OCL}}}
- ;OCL{{{ maze-step
- (deffun maze-step (
- @if-using (HIDE_SEARCH) screen-off @fi
- add-mode-overwrite
- set maze-state 1
- set maze-dir 0
- if =(maze-begin-line 0) ( set maze-begin-line store-line ) fi
- goto-line-counter maze-begin-line
- search-forward "X newline-and-indent
- if not(test-char "X) (message-exit "no_destination-point) fi
- goto-line-counter maze-begin-line
- search-forward "| newline-and-indent
- forward-character
- set maze-state 2
- while not(test-char "X) (
- show-cursor 0
- set case-0 maze-state
- test-case
- case
- ;OCL{{{ state 2
- (=(case-2 0) (
- turn-left
- front-wall
- repeat 3(turn-left)
- if =(maze-front 0) (
- set maze-state 3
- ) else (
- set maze-state 4
- ) fi
- ))
- ;OCL}}}
- ;OCL{{{ state 3
- (=(case-3 0) (
- turn-left
- go
- set maze-state 2
- ))
- ;OCL}}}
- ;OCL{{{ state 4
- (=(case-4 0) (
- front-wall
- if =(maze-front 0)
- (set maze-state 5)
- else
- (repeat 3 (turn-left))
- fi
- ))
- ;OCL}}}
- ;OCL{{{ state 5
- (=(case-5 0) (
- go
- set maze-state 2
- ))
- ;OCL}}}
- default (message-exit "incorrect_maze_state)
- esac
- )
- delete-mode-overwrite
- @if-using (HIDE_SEARCH) screen-on redraw-display @fi
- ))
- ;OCL}}}
- @fi
-